﻿#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
namespace test_set//set底层是红黑树,存储数据为一个key值，且不重复存储相同的key值，正向迭代器是中序遍历且默认为升序
{
	template<class set>
	void Print_Set(set& s)//
	{
		for (auto& e : s)
			cout << e << " ";
		cout << endl;
	}
	void test_construct()//构造
	{
		set<int> s1;//空构造
		Print_Set(s1);
		int arr[] = { 9,5,7,6,4,3,7,6,4,10,3 };
		set<int> s2(arr, arr + sizeof(arr) / sizeof(int));//迭代器区间构造
		Print_Set(s2);
		set<int> s3 = s2;//拷贝构造
		Print_Set(s3);
		set<int> s4 = { 6,2,6,7,1,10,3,4,9,0,8,2 };//列表构造
		Print_Set(s4);
		s1 = s2;//赋值重载
		Print_Set(s1);
	}
	void test_iterator()//迭代器---set是双向迭代器，只支持++，--
	{
		set<int> s1 = { 1,5,7,9,10,55,36,4,8,2,3 };
		//正向迭代器---输出升序
		//set<int>::iterator it=s1.begin();
		auto it = s1.begin();
		while (it != s1.end())
		{ 
			//*it += 2;        //set的普通迭代器都不支持修改key值
			//it += 2; it -= 2;//双向迭代器不支持+和-
			cout << *it << " ";
			++it;
		}
		cout << endl;
		//反向迭代器---输出降序
		//set<int>::reverse_iterator rit = s1.rbegin();
		auto rit = s1.rbegin();
		while (rit != s1.rend())
		{
			cout << *rit << " ";
			++rit;
		}
	}
	void test_modifiy()
	{
		//insert
		set<int> s1;
		//插入单个元素，返回类型为pair<iterator,bool>,如果已经存在则不会插入，并返回值中bool为false
		s1.insert(5);
		//检查插入
		int arr[] = { 1,9,8,7,5,4,2,1,3,0,9 };
		for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
		{
			if (s1.insert(arr[i]).second == false)
				cout << "插入失败，s1内已经有:" << arr[i] << endl;
			else cout << "插入成功" << endl;
		}
		Print_Set(s1); cout << endl;
		//列表插入，已经在容器中存在的值不会插入
		set<int> s2;
		s2.insert({1, 5, 9, 7, 3, 7});
		Print_Set(s2);
		//迭代器区间插入
		set<int> s3;
		s3.insert(arr, arr + sizeof(arr) / sizeof(int));
		Print_Set(s3); cout << endl;
		//erase
		//删除⼀个迭代器位置的值,并返回原删除元素后一个元素位置的迭代器
		set<int> s4 = s3; Print_Set(s4);
		auto it = s4.erase(s4.begin());
		Print_Set(s4); cout << *it << endl;
		//删除val，返回删除元素的数量，对于set来说val不存在返回0，存在返回1 
		int i = 0;
		//while (cin >> i)
		//{
		//	if (s4.erase(i) == 0)
		//		cout << "s4中不存在该元素" << endl;
		//	else cout << "删除成功" << endl;
		//}
		Print_Set(s4);
		// 删除⼀段迭代器区间的值 
		set<int> s5 = s1; //Print_Set(s5);
		s5.erase(++s5.begin(), --s5.end()); //Print_Set(s5);
		// swap
		Print_Set(s5); Print_Set(s1);
		s5.swap(s1); Print_Set(s5); Print_Set(s1);
		// clear
		set<int> s6 = s5; Print_Set(s6);
		s6.clear(); Print_Set(s6);
	}
	void test_Operation()
	{
		int arr[] = { 9,5,7,6,6,3,2,0,10,1 };
		set<int> s1(arr, arr + sizeof(arr) / sizeof(int));
		//Print_Set(s1);
		// find---找到就返回该元素的迭代器，没有就返回end()
		// 用set的find时间为o(logN),是按二叉搜索树规则查找，用算法库则为o(N)，是按遍历查找
		//int i;
		//while (cin >> i)
		//{
		//	if (s1.find(i) == s1.end())
		//		cout << "s1中没有该元素" << endl;
		//	else cout << "查找成功" << endl;
		//}
		//查找+删除
		//while (cin >> i)
		//{
		//	if (s1.find(i) == s1.end())
		//		cout << "s1中没有该元素" << endl;
		//	else
		//	{
		//		s1.erase(i);
		//		cout << "删除成功" << endl;
		//		Print_Set(s1);
		//	}
		//}
		//算法库的查找---o(N) 
		//int i; cin >> i;
		//auto f = find(s1.begin(), s1.end(), i);
		//if (f != s1.end())
		//	cout << "查找成功" << endl;
		//else cout << "查找失败" << endl;
		// count(计数器)---返回某个元素的出现次数，在set中，只有0和1，为o(logN)
		// 利用count间接快速查找
		//int x; cin >> x;
		//if (s1.count(x))
		//	cout << "查找成功" << endl;
		//else cout << "查找失败" << endl;
		// 算法库---o(N)
		//int y; cin >> y;
		//if(count(s1.begin(),s1.end(),y))
		//	cout << "查找成功" << endl;
		//else cout << "查找失败" << endl;
		
		// lower_bound---返回大于等于val位置的迭代器
		// upper_bound---返回大于val位置的迭代器
		set<int> s2;
		for (int i = 0; i < 10; i++)
			s2.insert(i * 10);
		// 利用上述两个接口在s2中输出[45,75)区间内的所有数
		Print_Set(s2);
		auto it1 = s2.lower_bound(45);
		auto it2 = s2.upper_bound(75);
		while (it1 != it2)
		{
			cout << *it1 << " ";
			++it1;
		}
		it1 = s2.lower_bound(45);
		cout << endl;
		// 删除[55,95)区间内的所有数
		s2.erase(it1, it2); Print_Set(s2);
		// equal_range---返回相等元素的范围(pair<iterator,iterator>)---在set中用的不多，因为set是没有相等的元素
		auto p = s2.equal_range(0);
		s2.erase(p.first,p.second); Print_Set(s2);//删除所有的0，在set中大材小用，只删除一个0
	}
}
namespace test_multiset// 与set大致类似，只不过底层存储数据可以出现重复值
{
	void test()
	{
		// 相比set不同的是，multiset是排序，但是不去重 
		multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };
		auto it = s.begin();
		while (it != s.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
		// 相比set不同的是，x可能会存在多个，find查找中序的第⼀个 
		int x;
		cin >> x;
		auto pos = s.find(x);
		while (pos != s.end() && *pos == x)//把后续重复的都给打印
		{
			cout << *pos << " ";
			++pos;
		}
		cout << endl;
		// 相比set不同的是，count会返回x的实际个数 
		cout << s.count(x) << endl;
		// 相比set不同的是，erase给值时会删除所有的x 
		s.erase(x);
		for (auto e : s)
		{
			cout << e << " ";
		}
		cout << endl;

	}
}
int main()
{
	//test_set::test_construct();
	//test_set::test_iterator();
	//test_set::test_modifiy();
	//test_set::test_Operation();
	test_multiset::test();
	return 0;
}